//
//  main.cpp
//  SA
//
//

#include<iostream>
#include<cstring>
#include<string>
#include<stdlib.h>
#include<time.h>
#include<cmath>
#include <mpi.h>

using namespace std;

#define MAXN 64
#define servers 4
#define T     3000    //初始温度
#define EPS   1e-8    //终止温度
#define DELTA 0.98    //温度衰减率
#define LIMIT 10000   //概率选择上限
#define OLOOP 5    //外循环次数
#define ILOOP 75   //内循环次数

//string id[MAXN];  //字符串(10010100)
string s;

//int countOfServer[4] = {5,5,5,5};
int num = MAXN / servers;
int countOfServer[4] = {num, num, num, num};       //记录每个节点中字符串的个数
int a[MAXN];
int cft_num[MAXN];  //记录每个id的冲突值
int cft_server[servers];  //记录每个server的冲突值
double Ex[servers];  //记录每个server均值
double Dx[servers];  //记录每个server方差


int x;   //交换值
int y;   //交换值
int position_x;
int position_y;
string previous_x;


string temp_str = "0";

//string id[1000] = {"1110","0111","0111","1000","0101","1011","1011","1110","0010","0000","1100","1101","1010","1011","1111","0110","1010","0111","0100","1110","0101","0111","0001","1000","1110","0110","1100","0001","1010","0001","0101","0011","0001","1001","0101","0011","1001","1011","1000","1110","1100","0010","0000","1111","1011","0000","0000","1100","1010","1011","1110","1010","1101","0110","0100","0000","0100","1001","0101","0011","0001","1101","0111","0111","0111","1100","0101","1001","1011","1100","0011","0001","1111","1000","0011","0001","0011","1001","1011","0111","1100","0000","0110","0100","1000","0010","1100","1111","1101","1100","0011","0100","1111","1001","1011","0101","1101","1000","1111","0001","0000","1111","0110","1000","0010","0000","0101","0100","0011","1011","1011","0001","0010","0111","1010","0110","1000","0111","1100","0011","1000","1111","1000","0010","1110","0101","0110","1001","0000","0010","1001","0000","1010","0001","1000","0000","0011","1110","0011","0111","0110","0110","0011","1101","1100","1101","0100","1011","1010","0000","1000","0010","0011","0100","1110","1100","0000","1101","0010","1011","1001","0100","0111","1111","0100","1111","0011","0100","1110","0010","0000","1001","0001","1000","0000","0010","0101","1011","0010","1001","1010","0010","0101","1100","0011","1000","1101","0100","1011","0010","1100","0101","0111","0001","0110","1011","0010","1010","0001","1000","0001","0000","1010","0000","0100","1101","0100","1010","1110","0001","0010","0001","0110","1101","1101","0100","1001","0000","1100","0101","0000","1001","0000","0011","1000","0010","1001","1111","1110","0011","0001","1110","1111","1110","1100","1111","0001","0100","0101","1111","0100","1011","0101","1100","0011","1100","0110","1000","0101","1000","111001","110111","100001","011011","101111","100010","000011","001101","101010","111111","011010","100111","010011","100101","011100","011000","111001","101100","000110","100001","010100","110001","100101","010011","100110","111000","111011","000010","000011","111011","000000","001100","101010","111110","101011","010110","010000","000100","100101","010011","000111","010111","011101","111100","010110","011011","110000","110001","111110","000011","000100","111001","101101","111100","000001","100100","100000","101100","111111","011100","001101","001111","100110","110101","110110","001111","000100","001111","011010","000010","000001","010100","001110","111011","000100","100111","101001","101000","011111","000011","100011","111000","001011","100101","011010","010000","001010","010000","101000","011000","000000","111110","001101","110110","011000","111101","110011","010100","101110","100000","100000","100011","010011","101100","000011","010010","101110","010100","011111","110100","111100","110100","111000","100000","100100","011000","000000","100101","101100","101001","101000","100101","110000","111000","110101","001011","001011","000101","011100","010110","101100","101010","000110","000001","000010","100000","010011","010100","101011","100001","001000","010110","110111","010100","100100","001100","010100","001001","000000","111000","001010","011111","111000","110001","111011","111110","110011","110001","010001","011111","010010","110101","110000","111100","011010","000101","100001","100001","110101","011001","001101","101010","000110","000110","001000","101010","000010","011010","111011","001101","011100","101011","001000","111001","011011","010001","110010","101000","000110","000101","011101","100111","011001","010111","111001","101101","001110","100100","100101","010110","101101","110111","101001","111110","101000","110111","010110","111111","110101","001010","100101","000010","111100","001000","100110","100011","010100","000011","111101","001111","111000","001001","110100","110110","111111","100100","011001","101010","011001","101001","100111","101001","110110","110011","100010","011011","011101","110100","011110","100100","111110","101000","110101","010101","001101","100011","011011","110100","111011","010001","11100111","01111000","01011011","10111110","00100000","11001101","10101011","11110110","10100111","01001110","01010111","00011000","11100110","11000001","10100001","01010011","00011001","01010011","10011011","10001110","11000010","00001111","10110000","00001100","10101011","11101010","11010110","01000000","01001001","01010011","00011101","01110111","01111100","01011001","10111100","00110001","11111000","00110001","00111001","10110111","11000000","01100100","10000010","11001111","11011100","00110100","11111001","10110101","11011000","11110001","00001111","01101000","00100000","01010100","00111011","10110001","00100111","10100110","10000111","11000011","10001111","10000010","11100101","01101001","00000010","10010000","10100001","10000000","00111110","00110111","01100110","00111101","11001101","01001011","10100000","10000010","00110100","11101100","00001101","00101011","10010100","01111111","01001111","00110100","11100010","00001001","00011000","00000010","01011011","00101001","10100010","01011100","00111000","11010100","10110010","11000101","01110001","01101011","00101010","00011000","00010000","10100000","01001101","01001010","11100001","00100001","01101101","11010100","10010000","11000101","00001001","00000011","10000010","10011111","11100011","00011110","11111110","11001111","00010100","01011111","01001011","01011100","00111100","01101000","01011000","01100001","11010101","10010011","01101010","00011000","01100010","00101010","00001001","10101110","11001101","01110010","10110010","00111001","01101101","00011100","10101000","00011000","01010111","01100111","01100101","01111110","01101101","00111010","01001001","01010110","10110111","01111010","01111110","10100011","01110101","10111111","11010100","10101001","01000010","11110000","10001001","10100011","01010000","00111111","01001111","11100000","10011101","00110110","11111110","01000110","01101010","01100110","10011001","11101001","11011011","00111000","10011011","01110111","01000111","10100100","11111010","10001101","01010101","00110110","00110110","11110100","11101101","00010100","00111010","11100000","11011000","00111000","11001010","11111010","01101110","11001011","00001011","10100010","11101011","01001100","00101011","01010111","11000110","01110101","11110010","01000000","10101100","10110011","01111010","00000111","00100101","01101001","10111111","11110010","01111011","10101011","01011001","01110001","10011111","00010010","00110100","10011011","01001111","10011100","10010111","00100110","11001011","01100110","10111000","00000001","00110110","00001011","01001001","10110001","11100101","00101110","01011110","01111101","10001110","00100101","10001100","11110111","01100001","01110010","00110001","10001000","00011001","11001001","00010111","00111001","1110011101","1110000101","1011101111","1000100000","1100110110","1010111111","0110101001","1101001110","0101011100","0110001110","0110110000","0110100001","0101001100","0110010101","0011100110","1110001110","1100001000","0011111011","0000000011","0010101011","1110101011","0101100100","0000010010","0101010011","0001110101","1101110111","1100010110","0110111100","0011000111","1110000011","0001001110","0110110111","1100000001","1001001000","0010110011","1111011100","0011010011","1110011011","0101110110","0011110001","0000111101","1010000010","0000010101","0000111011","1011000100","1001111010","0110100001","1111000011","1000111110","0000101110","0101011010","0100000010","1001000010","1000011000","0000001111","1000110111","0110011000","1111011100","1101010010","1110100000","1000001000","1101001110","1100000011","0100101011","1001010001","1111110100","1111001101","0011100010","0000100100","0110000000","0010010110","1100101001","1010001001","0111000011","1000110101","0010110010","1100010101","1100010110","1011001010","1000011000","0001000010","1000000100","1101010010","1011100001","0010000101","1011011101","0100100100","0011000101","0000100100","0000111000","0010100111","1111100011","0001111011","1111101100","1111000101","0001011111","0100101101","0111000011","1100011010","0001011000","0110000111","0101011001","0011011010","1000011000","0110001000","1010100000","1001101011","1011001101","0111001010","1100100011","1001011011","0100011100","1010100000","0110000101","0111011001","1101100101","0111111001","1011010011","1010010010","0101010110","1011011101","1110100111","1110101000","1101110101","1011111111","0101001010","1001010000","1011110000","1000100110","1000110101","0000001111","1101001111","1110000010","0111010011","0110111111","1001000110","0110101001","1001101001","1001111010","0111011011","0011100010","0110110111","0111010001","1110100100","1111101010","0011010101","0101001101","1000110110","1111010011","1011010001","0100001110","1011100000","1101100000","1110001100","1010111110","1001101110","1100101100","0010111010","0010111010","1101001100","0010101101","0101111100","0110011101","0111110010","0100000010","1011001011","0011011110","1000000111","0010010101","1010011011","1111111100","1001111011","1010101101","0110010111","0001100111","1100010010","0011010010","0110110100","1111100111","0010010111","0010011011","0010110110","0110101110","0000000001","0011011000","0010110100","1001101100","0111100101","0010111001","0111100111","1101100011","1000100101","1000110011","1101110110","0001011100","1000110001","1000100000","0110011100","1001000101","1100111001","0110111001","1101011001","1000010000","1010101101","1001111011","0010111100","0101110011","0011001001","1000011101","0101111100","0010101100","0100100011","1101001001","0010000000","0110011010","1011110111","0001011001","0111010011","0011010101","1001111101","0000000111","1011100100","0101011011","1000101100","1000111101","0001101100","1111011100","0001111011","1100000110","0011101011","1000110111","0001011001","0101001001","0110100001","0100011001","1110001000","1100011010","0010110100","0011100101","1110000110","0111101001","1101110011","1111000010","1001000110","0110011111","1110011111","1100101010","1101111001","1110011110","1101111110"};

string id[64] = {"1110", "0111", "0111", "1000", "0101", "1011", "1011", "1110", "0010", "0000", "1100", "1101", "1010",
                 "1011", "1111", "0110", "1010", "0111", "0100", "1110", "0101", "0111", "0001", "1000", "1110", "0110",
                 "1100", "0001", "1010", "0001", "0101", "0011", "0001", "1001", "0101", "0011", "1001", "1011", "1000",
                 "1110", "1100", "0010", "0000", "1111", "1011", "0000", "0000", "1100", "1010", "1011", "1110", "1010",
                 "1101", "0110", "0100", "0000", "0100", "1001", "0101", "0011", "0001", "1101", "0111", "0111"};


/*/mine/*/
int my_rank, comm_sz;              //获取进程号
/*/mine/*/

//输出每个服务器的字符串
void print_id() {
    int t = 0;
    for (int i = 0; i < servers; i++) {
        cout << "server " << i << " ";
        for (int j = t; j < t + countOfServer[i]; j++)
            cout << id[j] << " ";
        cout << endl;
        t += countOfServer[i];
    }
}

//比较字符串
int compare(string s1, string s2) {
    int res, ans = 1;
    int l1, l2, len;
    l1 = (int) s1.length();
    l2 = (int) s2.length();

    if (l1 != l2) {
        if (l1 > l2)
            len = l2;
        else
            len = l1;

        for (int i = 0; i < len; i++) {
            if (int(s1.c_str()[i]) != int(s2.c_str()[i])) {
                ans = 0;
                break;
            }
        }
        //res = s1.compare(0, len-1, s2, 0, len-1);
    } else {
        if (l1 == 2) {
            for (int i = 0; i < 2; i++) {
                if (int(s1.c_str()[i]) != int(s2.c_str()[i])) {
                    ans = 0;
                    break;
                }
            }
        } else {
            for (int i = 0; i < l1 - 2; i++) {
                if (int(s1.c_str()[i]) != int(s2.c_str()[i])) {
                    ans = 0;
                    break;
                }
            }
        }
        //res = s1.compare(0, l1-3, s2, 0, l2-3);
    }
    return ans;
} //输出0不等，不冲突；输出1相等，冲突



//计算每一个串的冲突值
void conflict() {
    //div();
    memset(cft_num, 0, MAXN);
    int num_ans;
    int ser_ans;
    int count = 0;
    for (int i = 0; i < servers; i++) {
        num_ans = 0;
        ser_ans = 0;

        for (int j = count; j < count + countOfServer[i]; j++) {
            int t = count + countOfServer[i];
            while ((t--) > (j)) {

                num_ans += compare(id[j], id[t]);
                //cout<<j<< " "<<t<<" "<<ans<<endl;
            }
            cft_num[j] = num_ans - 1;         //cft_num记录每个id的冲突值
            num_ans = 0;
            ser_ans += cft_num[j];
        }
        cft_server[i] = ser_ans;            //记录每个server的冲突值
        count += countOfServer[i];
    }
    /*for(int i=0; i<MAXN; i++)
        cout<<cft_num[i]<<endl;
    for(int i=0; i<servers; i++)
        cout<<cft_server[i]<<endl;
    cout<<endl<<endl;*/
    //EX();
    //DX();
}

//每一个server均值
double EX() {
    double ans = 0;
    for (int i = 0; i < servers; i++) {
        Ex[i] = (double) cft_server[i] / countOfServer[i];
        ans += Ex[i];
    }
    return ans;
}

void print_EX() {
    for (int i = 0; i < servers; i++)
        cout << "server" << i << "dejunzhi:" << Ex[i] << endl;
}


//每一个server方差
double DX() {
    double ans;
    double sum = 0;
    int count = 0;
    for (int i = 0; i < servers; i++) {
        ans = 0.0;
        for (int j = count; j < count + countOfServer[i]; j++)
            ans += pow((cft_num[j] - cft_server[i]), 2);
        Dx[i] = ans / countOfServer[i];
        sum += Dx[i];
        count += countOfServer[i];
    }
    return sum;
}

void print_DX() {
    for (int i = 0; i < servers; i++)
        cout << "server" << i << "defangcha:" << Dx[i] << endl;
}


//随意交换两个字符串位置
void getNext() {

    x = (rand() + my_rank * 10) % MAXN;         // 因为使用同一随机种子, 所以多个进程产生的随机数相同,因此使用my_rank做调整
    y = (rand() + my_rank * 10) % MAXN;
    while (x == y) {
        x = rand() % MAXN;
        y = rand() % MAXN;
    }

    //cout<<x<<" "<<y<<endl;
    int count = 0;

    //判断id[x]所在server
    for (int i = 0; i < servers; i++) {
        if (x <= count + countOfServer[i]) {
            countOfServer[i]--;
            position_x = i;             // position_x记录的是x属于哪个服务器
            break;
        }
        count += countOfServer[i];

    }
    //判断id[y]所在server
    count = 0;
    for (int i = 0; i < servers; i++) {
        if (y <= count + countOfServer[i]) {
            countOfServer[i]++;
            position_y = i;
            break;
        }
        count += countOfServer[i];
    }


    previous_x = id[x];         // previous_x是一个用于交换时临时存储的变量, 作用相当于temp
    if (x > y) {
        for (int i = x; i > y; i--) {
            id[i] = id[i - 1];
        }

        id[y] = previous_x;

    } else {
        for (int i = x; i < y; i++) {
            id[i] = id[i + 1];
        }
        id[y] = previous_x;
    }

    //id[x].swap(id[y]);
    conflict();
}


void SA() {
    double t = T;
    srand(time(NULL));

    double cur_EX = EX();       // 当前进程的ex值
    double cur_min_EX_ofallthread=0;  // 某温度的某次遍历之后,多个进程中最小的ex值
    double pre_min_EX_ofallthread=0;  // 上一步中,多个进程中最小的ex值
    double distance_EX=0;           // 两次ex之间的差值
    double new_EX;

    //double cur_DX = DX();
    //double new_DX;

    int P_L = 0;    // 连续找到更差结果的次数
    int P_F = 0;    // while循环次数
    while (1)       //外循环，主要更新参数t，模拟退火过程
    {
        while (1) {

            for (int i = 0; i < ILOOP / comm_sz; i++)    //内循环，寻找在一定温度下的最优值
            {
                getNext();
                new_EX = EX();
                //new_DX = DX();

                double dE = new_EX - cur_EX;
                //double dE = new_DX - cur_DX;

                if (dE < 0)   //如果找到更优值，直接更新
                {
                    cur_EX = new_EX;
                    //cur_DX = new_DX;

                    P_L = 0;
                    P_F = 0;
                } else {
                    double rd = rand() / (RAND_MAX + 1.0);

                    // dE取负数才有可能接受更差解,否则e>1
                    double e = exp(-dE / t);
                    if (e > rd && e < 1)   //如果找到比当前更差的解，以一定概率接受该解，并且这个概率会越来越小
                        cur_EX = new_EX;
                        //cur_DX = new_DX;
                    else {
                        if (x > y) {
                            for (int i = y; i < x; i++) {
                                id[i] = id[i + 1];
                            }
                            id[x] = previous_x;
                        } else {
                            for (int i = y; i > x; i--) {
                                id[i] = id[i - 1];
                            }
                            id[x] = previous_x;
                        }
                        countOfServer[position_x]++;
                        countOfServer[position_y]--;

                    }

                    P_L++;
                }
/*                if (P_L > LIMIT) {
                    P_F++;
                    break;
                }*/
            }
            if(my_rank==0)  pre_min_EX_ofallthread=cur_min_EX_ofallthread;
            MPI_Barrier(MPI_COMM_WORLD);
            //MPI_Reduce(&cur_EX,&cur_min_EX_ofallthread,1,MPI_DOUBLE,MPI_MIN,0,MPI_COMM_WORLD);  //聚集起来，选取最小的付给cur_min_EX_ofallthread，获得本次的cur_min_EX_ofallthread
            //if(my_rank==0)  distance_EX=pre_min_EX_ofallthread-cur_min_EX_ofallthread;
            if(my_rank!=0)
            {
                MPI_Send(&cur_EX,1,MPI_DOUBLE,0,0,MPI_COMM_WORLD);
            }
            if(my_rank==0)
            {
                double temp_EX_arr[MAXN];
                double temp_EX;
                temp_EX_arr[0]=cur_EX;
                for(int q=1;q<comm_sz;q++)
                {
                    MPI_Recv(&temp_EX,1,MPI_DOUBLE,q,0,MPI_COMM_WORLD,MPI_STATUS_IGNORE);
                    temp_EX_arr[q]=temp_EX;
                }
                // 求最小的EX的坐标位置
                int index=0;
                cur_min_EX_ofallthread=temp_EX_arr[0];
                for(int q=1;q<comm_sz;q++)
                {
                    if(temp_EX_arr[q]<temp_EX)
                    {
                        cur_min_EX_ofallthread=temp_EX_arr[q];
                        index=q;
                    }
                }
                // 利用最小的EX求distance_EX
                distance_EX=cur_min_EX_ofallthread-pre_min_EX_ofallthread;
            }
            MPI_Bcast(&distance_EX,1,MPI_DOUBLE,0,MPI_COMM_WORLD);
            if(distance_EX<0.1){
                cout <<"distance_EX:"<< distance_EX << "  in rank: " << my_rank << endl;
                break;
            }
        }
        if (P_F > OLOOP || t < EPS)
            break;
        t *= DELTA;
    }


    /*/mine/*/
    double *trans_EX;
    double ans_EX = 999999999;
    int trans_num = 1;
    trans_EX = (double *) malloc(comm_sz * sizeof(double));
    //MPI_Gather(cur_EX,trans_num,MPI_DOUBLE,ans_EX,trans_num,MPI_DOUBLE,0,MPI_COMM_WORLD);
    MPI_Gather(&cur_EX, trans_num, MPI_DOUBLE, trans_EX, trans_num, MPI_DOUBLE, 0,
               MPI_COMM_WORLD);      //把各个进程的局部最优解收集起来
    for (int i = 0; i < comm_sz; i++) {
        cout << "trans_EX:" << trans_EX[i] << " in rank" << my_rank << "   ";        // 因为是通过0号进程收集， 所以其他进程中的ans_EX时任意数
        if (trans_EX[i] < ans_EX)
            ans_EX = trans_EX[i];
    }
    cout << endl << endl;
    cout << "final ex=" << ans_EX << endl;

    /*/mine/*/



}


int main() {
    //print_id();


    clock_t startTime, endTime;
    startTime = clock();


    /*/mine/*/
    MPI_Init(NULL, NULL);               //初始化
    MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); //获取进程号
    MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
    srand(time(0) + my_rank * 10);                                //以时间为随机数种子产生随机数
    /*/mine/*/

    cout << endl;
    conflict();                // 计算每个文件的冲突值
    EX();
    print_EX();
    cout << "computing in thread" << my_rank << "..." << endl;

    /*/mine/*/
    //MPI_Barrier(MPI_COMM_WORLD);
    /*/mine/*/

    SA();
    for (int i = 0; i < MAXN; i++)
        cout << id[i] << " ";
    cout << endl;

    for (int i = 0; i < 4; i++) {
        cout << countOfServer[i] << ":countOfServer" << endl;
    }

    EX();
    print_EX();

    /*/mine/*/
    MPI_Finalize();

    endTime = clock();
    cout << "run time:" << (double) (endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;

    return 0;
    /*/mine/*/

}
